#include <iostream>
#include <vector>
using namespace std;

// 第1种计算最大收益的方法（动态规划，使用数组记录中间状态）
int plan1(vector<int>& E) {
    int n = E.size();

    // dp[i]表示从E[0..i]中取得的最大收益
    vector<int> dp(n, 0);

    for (int i = 0; i < n; ++i) {
        // 分支1：第i天不出行，所以收益为0，总收益跟之前一样
        if (i > 0)  // 代码细节：不加这个判断下一句有可能数组越界
            dp[i] = dp[i - 1];

        // 分支2：当天出行，这样E[i-1]就不能出行，总收益加上dp[i-2]
        int money = E[i];
        if (i >= 2)
            money += dp[i - 2];
        if (money > dp[i])
            dp[i] = money;
    }
    // 备忘录的最后一个值为答案
    return dp[n - 1];
}

// 优化：第2种计算最大收益的方法（滚动数组思想）
int plan(vector<int>& E) {
    // dp1表示到当天为止的最大收益
    // dp2表示到前一天为止的最大收益
    int dp1 = 0, dp2 = 0;

    for (int x : E) {
        // 缓存滚动后的前一天数据
        int temp = dp1;

        // 计算当天数据，计算方式和之前一样
        dp1 = max(dp1, x + dp2);

        // 还原缓存的数据到dp2
        dp2 = temp;
    }
    // 计算到最后的dp1为最终答案
    return dp1;
}

int main() {
    vector<int> E = { 7, 9, 7, 1, 6, 8, 3, 4 };
    int result = plan(E);
    cout << "最大收益: " << result << endl;
    return 0;
}